package leetcode.editor.cn.q0xx

class Q69 {
    fun mySqrt(x: Int): Int {
        if (x == 0) return 0
        if (x == 1) return 1
        var low = 0
        var high = x
        var ans = -1
        while (low <= high) {
            val mid = low + (high - low) / 2
            if ((mid.toLong() * mid) <= x.toLong()) {
                ans = mid
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
        return ans
    }
}